package org.chnxi.study.datastructrues.tree;

/**
 * 树节点
 * @param <E>
 */
public class TreeNode<E>{
    private E e; //节点元素
    private TreeNode<E> left; //左节点
    private TreeNode<E> right; //右节点

    public E getE() {
        return e;
    }

    public void setE(E e) {
        this.e = e;
    }

    public TreeNode<E> getRight() {
        return right;
    }

    public void setRight(TreeNode<E> right) {
        this.right = right;
    }

    public TreeNode<E> getLeft() {
        return left;
    }

    public void setLeft(TreeNode<E> left) {
        this.left = left;
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        //输出当前节点
        System.out.println(this);
        //递归左子树
        if(this.left != null){
            this.left.preOrder();
        }
        //递归右子树
        if(this.right != null){
            this.right.preOrder();
        }
    }

    /**
     * 使用前序遍历进行查找
     * @param e 待查找对象
     * @return
     */
    public TreeNode<E> searchByPreOrder(E e){
        System.out.println("辅助输出：进入前序遍历查找...");
        //先比较当前节点是不是
        if(this.getE().equals(e)){
            return this;
        }

        //存储查找结果
        TreeNode<E> result = null;

        //递归左子树进行查找
        if(this.left != null){
            result = this.left.searchByPreOrder(e);
        }
        //确认左子树是否找到
        if(result != null){
            return result;
        }

        //递归右子树进行查找
        if(this.right != null){
            result = this.right.searchByPreOrder(e);
        }

        return result;
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        //递归左子树
        if(this.left != null){
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //递归右子树
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    /**
     * 使用中序遍历进行查找
     * @param e 待查找的元素
     * @return
     */
    public TreeNode<E> searchByInfixOrder(E e){
        TreeNode<E> result = null;

        //递归左子树
        if(this.left != null){
            result = this.left.searchByInfixOrder(e);
        }
        //确认左子树是否找到
        if(result != null){
            return result;
        }

        System.out.println("辅助输出：进入中序遍历查找...");
        //先比较当前节点是不是
        if(this.getE().equals(e)){
            return this;
        }

        //递归右子树
        if(this.right != null){
            result = this.right.searchByInfixOrder(e);
        }

        return result;
    }

    /**
     * 后序遍历
     */
    public void postOrder(){
        //递归左子树
        if(this.left != null){
            this.left.postOrder();
        }
        //递归右子树
        if(this.right != null){
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }

    /**
     * 使用后序遍历查找
     * @param e 待查找元素
     * @return
     */
    public TreeNode<E> searchByPostOrder(E e){
        TreeNode<E> result = null;

        //递归左子树
        if(this.left != null){
            result = this.left.searchByPostOrder(e);
        }
        //确认左子树是否找到
        if(result != null){
            return result;
        }

        //递归右子树
        if(this.right != null){
            result = this.right.searchByPostOrder(e);
        }
        //确认右子树是否找到
        if(result != null){
            return result;
        }

        System.out.println("辅助输出：进入后序遍历查找...");
        //比较当前节点是不是
        if(this.getE().equals(e)){
            return this;
        }

        return result;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "e=" + e +
                '}';
    }

    /**
     * 递归删除节点
     * @param e
     * @return 删除成功返回true，没删除返回false
     */
    public boolean delTreeNode(E e){

        //判断左子节点是否匹配
        if(this.left != null && this.left.getE().equals(e)){
            this.left = null;
            return true;
        }
        //判断右子节点是否匹配
        if(this.right != null && this.right.getE().equals(e)){
            this.right = null;
            return true;
        }

        boolean result = false;

        //向左子树进行递归删除
        if(this.left != null){
            result = this.left.delTreeNode(e);
        }
        if(result){
            return result;
        }
        //向右子树递归删除
        if(this.right != null){
            result = this.right.delTreeNode(e);
        }

        return result;
    }
}